package com.example.demo.leetcode.jianzhi;

/**
 * @author xujimou
 * @version 2.0
 * @Description 定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
 * @date 2021/8/11 17:43
 */
public class Node_包含min函数的栈 {


    static class Node{
        int value;
        Node next;
        public Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }
    }


    static class MinStack {

        Node head;
        int min = Integer.MIN_VALUE;
        int size;
        /** initialize your data structure here. */
        public MinStack() {
            head=new Node(0,null);
            size = 0;
        }

        public void push(int x) {
            Node temp = head;
            head = new Node(x,temp);
            min = Math.min(min,x);
            size++;
        }

        public int pop() {
            if(size == 0){
                throw new RuntimeException("栈为空");
            }
            size--;
            int val = head.value;
            head = head.next;
            return val;
        }

        public int top() {
            if(size == 0){
                throw new RuntimeException("栈为空");
            }
            int val = head.value;
            return val;
        }

        public int min() {
            return min;
        }
    }

    public static void main(String[] args) {

        MinStack stack = new MinStack();
        stack.push(1);
        stack.push(2);
        stack.push(3);

        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
    }


}
